"""
    This program is an AC automaton which consist of trie tree data
structure & KMP string matching algorithm. To read the source code, 
you'd better konw the trie and just heard KMP.
    At first, the program add words into trie tree use 'addWord'
methord, then use 'make' methord encode the state for every node and
generate a state table. At last, fill the 'template.v' verilog template
by ACautomaton's data.

    the state table use Adjacency list like List to represent the
state transition:
    1. List id is the current state
    2. List element is tuples like (char, next_state). When char is
        None, it represents current char is unmatched.
    3. shuch as List[5] = [('d', 6), ('c', 3), (None, 2)] represents
       state  char   next_state
       5  ->  d      6
           |  c      3
           |  other  2
"""
from jinja2 import Environment, FileSystemLoader
from random import randint
import math, hashlib
 
class TrieNode(object):

    def __init__(self): 
        self.children = {}
        self.is_word = False
        self.fail = None
        self.state = None
        self.word = ''          #if is_word is True it's a word else is ''
    
    def __repr__(self):
        return "<TrieNode %d>" % id(self)
    
    def fold(self, f, a):
        b = f(a, self)
        for node in self.children.values():
            b = node.fold(f, b)
        return b

    def show(self, depth=0, c=None):
        indent = depth*4*' '
        if c is not None:
            print(indent+'|%c-<%d-%d>' % (c, self.state, self.fail.state), end='')
            if self.is_word:
                print('  '+self.word)
            else:
                print()
        for c, node in self.children.items():
            node.show(depth+1, c)

class ACautomaton(object):

    def __init__(self):
        self.root = TrieNode()
        self.state_table = []
        #words: [(word, ouput_encode, state), (...), ...]
        #words is used to assign the output port 'match' 's value
        self.words = []
        self.M = 0          #words' length
        self.made = False
        
    def addWord(self, word):
        node = self.root
        for c in word:
            if c not in node.children:
                node.children[c] = TrieNode()
            node = node.children[c]
        node.is_word = True
        node.word = word
        self.made = False
    
    def make(self):
        quee = []
        #set root's children's fail as root
        for c, node in self.root.children.items():
            node.fail = self.root
            quee.append(node)
        
        #process other nodes
        while quee:
            t = quee.pop()
            for c, node in t.children.items():
                quee.append(node)
                f = t.fail
                while c not in f.children:
                    if f.fail is None:
                        break
                    f = f.fail
                node.fail = f.children.get(c, self.root)
        
        #encode state for every node
        quee.append(self.root)
        state = 0
        while quee:
            node = quee.pop()
            node.state = state
            state += 1
            quee.extend(node.children.values())
        
        #caculate someother data use for filling template
        self._setStateTable()
        self._setWords()
        self.made = True
    
    def _setStateTable(self):
        #add root informations into state table
        state_table = [[(c, n.state) for c, n in self.root.children.items()]]
        state_table[0].append((None, 0))
        
        quee = [node for node in self.root.children.values()]
        while quee:
            node = quee.pop()
            next_state_list = [(c, n.state) for c, n in node.children.items()]
            for c, n in node.fail.children.items():
                if c not in node.children:
                    next_state_list.append((c, n.state))
            next_state_list.append((None, 0))
            state_table.append(next_state_list)
            quee.extend(node.children.values())
        self.state_table = state_table
    
    def _setWords(self):
        #see 'TrieNode.fold' is helpful to understand the next line
        is_word_nodes = self.root.fold(lambda a, n: a+[n] if n.is_word else a, [])
        #caculate how wide the output port can contain all words
        self.M = math.ceil(math.log(len(is_word_nodes)+1, 2))
        for i in range(0, len(is_word_nodes)):
            n = is_word_nodes[i]
            self.words.append((n.word, i+1, n.state))
    
    def genVerilog(self):
        assert self.made==True, 'should call make() after add words'
        env = Environment(loader=FileSystemLoader('templetes'))
        
        #generate verilog design file
        c = {
            'states'   : self.state_table,
            'N'        : len(self.state_table),
            'words'    : self.words,
            'M'        : self.M
        }
        template = env.get_template('templete.v')
        vfile = open("verilog/acautomaton.v","w")
        vfile.write(template.render(**c))
        vfile.close()
        
        #generate testbench file
        #firstly generate the input data 'test_data'
        words = [w[0] for w in self.words]
        test_data = "Author: misaka10418"
        for w in words:
            m = hashlib.md5(w.encode('utf-8'))
            test_data += w + m.hexdigest()[:12]
        c  = {
            'M': self.M,
            'test_data': test_data,
            'test_data_len': len(test_data)
        }
        template = env.get_template('templete_tb.v')
        vfile = open("verilog/acautomaton_tb.v","w")
        vfile.write(template.render(**c))
        vfile.close()
    
    def typeTire(self):
        print('Trie tree: char-<state-fail>')
        print('<root>')
        self.root.show()
        print()
    
    def typeTable(self):
        for i in range(0,len(self.state_table)):
            print("%4d -> " % i, end='')
            for state in self.state_table[i]:
                print(state, end=' ')
            print('\n')